#include <iostream>
#include<windows.h>
#include<stdlib.h>
using namespace std;
int* a, * b;
const int n = 300000;//规定是偶数，方便二路算法计算
void recursion(int n)
{
    if (n == 1)
        return;
    else
    {
        for (int i = 0; i < n; i++)
            a[i] += a[n - i - 1];
        n = n / 2;
        recursion(n);
    }
}


int main()
{
    a = new int [n];
    b = new int[n];
    //初始化记录数据的数组
    for (int i = 0; i < n; i++)
    {
        a[i] = rand() % 100;
        b[i] = a[i];
    }
    //多链路是算法
    int solution2 = 0;
    int* solution22 = new int[2];
    solution22[0] = 0;
    solution22[1] = 0;

    long long head2, tail2, freq2;
    QueryPerformanceFrequency((LARGE_INTEGER*)&freq2);
    QueryPerformanceCounter((LARGE_INTEGER*)&head2);
    for (int i = 0; i < n-1; i = i+2)
    {
        solution22[0] += a[i];
        solution22[1] += a[i+1];
    }
    solution2 = solution22[0] + solution22[1];
        QueryPerformanceCounter((LARGE_INTEGER*)&tail2);
    cout << "多链路式: " << (tail2 - head2) * 1000.0 / freq2 << "ms" << endl;


    //普通算法
    int solution1 = 0;
    long long head1, tail1, freq1;
    QueryPerformanceFrequency((LARGE_INTEGER*)&freq1);
    QueryPerformanceCounter((LARGE_INTEGER*)&head1);
    for (int i = 0; i < n; i++)
        solution1 += a[i];
    QueryPerformanceCounter((LARGE_INTEGER*)&tail1);
    cout << "普通算法耗时: " << (tail1 - head1) * 1000.0 / freq1 << "ms" << endl;



    //递归算法
    long long head3, tail3, freq3;
    QueryPerformanceFrequency((LARGE_INTEGER*)&freq3);
    QueryPerformanceCounter((LARGE_INTEGER*)&head3);
    recursion(n);
    QueryPerformanceCounter((LARGE_INTEGER*)&tail3);
    cout << "递归算法耗时: " << (tail3 - head3) * 1000.0 / freq3 << "ms" << endl;

    //二重循环
    long long head4, tail4, freq4;
    QueryPerformanceFrequency((LARGE_INTEGER*)&freq4);
    QueryPerformanceCounter((LARGE_INTEGER*)&head4);
    for (int m = n; m > 1; m /= 2)
        for (int i = 0; i < m / 2; i++)
            a[i] = a[i * 2] + a[i * 2 + 1];
    QueryPerformanceCounter((LARGE_INTEGER*)&tail4);
    cout << "二重循环耗时: " << (tail4 - head4) * 1000.0 / freq4 << "ms" << endl;

}